#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
struct ListNode {
    int val;
    struct ListNode* next;
};
   struct ListNode* partition(struct ListNode* pHead, int x) {
        struct ListNode* lesshead, * lesstail, * gratetail, * gratehead;
        struct ListNode* cur = pHead;
        lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
        gratehead = gratetail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lesstail->next = NULL;
        gratetail->next = NULL;
        while (cur)
        {
            if (cur->val < x)
            {
                lesstail->next = cur;
                lesstail = cur;
            }
            else
            {
                gratetail->next = cur;
                gratetail = cur;
            }
            cur = cur->next;
        }
        lesstail->next = gratehead->next;
        gratetail->next = NULL;
        struct ListNode* newhead = lesshead->next;
        free(lesshead);
        free(gratehead);
        return newhead;
    }